#pragma once
#include <iostream>

template <class T>
struct BinarySearchTreeNode
{
    BinarySearchTreeNode(const T &val, BinarySearchTreeNode<T> *left = nullptr, BinarySearchTreeNode<T> *right = nullptr)
        : _val(val), _left(left), _right(_right)
    {
    }
    T _val;
    BinarySearchTreeNode<T> *_left;
    BinarySearchTreeNode<T> *_right;
};

template <class T>
class BinarySearchTree
{
public:
    typedef BinarySearchTreeNode<T> Node;

private:
    Node *_root;

private:
    void _insert(const T &t);
    void _insertR(Node *&root, const T &t);

    Node *_find(const T &t);

    bool _erase(const T &t);
    bool _eraseR(Node *&root, const T &t);

    void _InOrder(Node *root);
    Node* copy(Node* root);
    void destory(Node*& root);

public:
    BinarySearchTree() : _root(nullptr) {}
    BinarySearchTree(const BinarySearchTree& other) { _root = copy(other._root);}

    ~BinarySearchTree() {destroy(_root);}

    // 增删查改
    void insert(const T &t, bool recursion = true);
    Node *find(const T &t, bool recursion = false);
    bool erase(const T &t, bool recursion = true);

    void InOrder();

};
template <class T>
void BinarySearchTree<T>::InOrder()
{
    _InOrder(_root);
}
template <class T>
void BinarySearchTree<T>::_InOrder(Node* root)
{
    if (root == nullptr)
        return;
    _InOrder(root->_left);
    std::cout << root->_val << ' ';
    _InOrder(root->_right);
}
template <class T>
typename BinarySearchTree<T>::Node* BinarySearchTree<T>::copy(Node* root)
{
    if (root == nullptr)
        return nullptr;
    Node *copyroot = new Node(root->_val);
    copyroot->_left = copy(root->_left);
    copyroot->_right = copy(root->_right);
    return copyroot;
}

template <class T>
void BinarySearchTree<T>::destory(Node*& root)
{
    if (root == nullptr)
        return;
    destory(root->_left);
    destory(root->_right);
    delete root;
}

// 增删查改
template <class T>
void BinarySearchTree<T>::insert(const T &t, bool recursion)
{
    if (recursion)
    {
        _insertR(_root, t);
    }
    else
    {
        _insert(t);
    }
}

template <class T>
typename BinarySearchTree<T>::Node* BinarySearchTree<T>::find(const T &t, bool recursion)
{
    if (recursion)
    {
        return _find(t);
    }
    else
    {
        return _find(t);
    }
}

template <class T>
bool BinarySearchTree<T>::erase(const T &t, bool recursion)
{
    if (recursion)
    {
        return _eraseR(_root, t);
    }
    else
    {
        return _erase(t);
    }
}
//------------------------------------------------------------------------

template <class T>
void BinarySearchTree<T>::_insert(const T &t)
{
    if (_root == nullptr)
    {
        _root = new Node(t);
        return;
    }
    Node *cur = _root;
    Node *prev = nullptr;
    while (cur)
    {
        if (t < cur->_val)
        {
            prev = cur;
            cur = cur->_left;
        }
        else if (t > cur->_val)
        {
            prev = cur;
            cur = cur->_right;
        }
        else
        {
            // t已存在，之间返回
            return;
        }
    }
    Node *tmp = new Node(t);
    if (t > prev->_val)
        prev->_right = tmp;
    else
        prev->_left = tmp;
}

template <class T>
void BinarySearchTree<T>::_insertR(typename BinarySearchTree<T>::Node* &root, const T &key)
{
    if (root == nullptr)
    {
        root = new Node(key);
        return;
    }
    if (root->_val > key)
    {
        _insertR(root->_left, key);
    }
    else if (root->_val < key)
    {
        _insertR(root->_right, key);
    }
    else
    {
        return;
    }
}

template <class T>
typename BinarySearchTree<T>::Node* BinarySearchTree<T>::_find(const T &t)
{
    Node *cur = _root;
    while (cur)
    {
        if (t > cur->_val)
        {
            cur = cur->_right;
        }
        else if (t < cur->_val)
        {
            cur = cur->_left;
        }
        else
        {
            return cur;
        }
    }
    return nullptr;
}

template <class T>
bool BinarySearchTree<T>::_erase(const T &t)
{
    if (_root == nullptr)
        return false;
    Node *cur = _root;
    Node *prev = nullptr;
    while (cur)
    {
        if (t < cur->_val)
        {
            prev = cur;
            cur = cur->_left;
        }
        else if (t > cur->_val)
        {
            prev = cur;
            cur = cur->_right;
        }
        else
        {
            // 找到
            break;
        }
    }
    // t不在二叉搜索树中，无法删除
    if (nullptr == cur)
        return false;
    // t在，分以下情况进行删除
    if (nullptr == cur->_left)
    {
        // 情况1：当前节点只有右孩子或者左右孩子为空---可直接删除
        if (prev == nullptr)
        {
            // 1. prev == nullptr --> cur == _root
            _root = _root->_right;
        }
        else if (prev->_left == cur)
        {
            // 2. prev != nullptr --> 判断cur是prev左还是右
            prev->_left = cur->_right;
        }
        else
        {
            prev->_right = cur->_right;
        }
    }
    else if (nullptr == cur->_right)
    {
        // 情况2：当前节点只有左孩子或者左右孩子为空---可直接删除
        if (prev == nullptr)
        {
            // 1. prev == nullptr --> cur == _root
            _root = _root->_left;
        }
        else if (prev->_left == cur)
        {
            // 2. prev != nullptr --> 判断cur是prev左还是右
            prev->_left = cur->_left;
        }
        else
        {
            prev->_right = cur->_left;
        }
    }
    else
    {
        // 情况3：当前节点左右孩子都存在，直接删除不好删除，可以在其子树中找一个替代结点，
        // 找其左子树中的最大节点，即左子树中最右侧的节点，或者在其右子树中最小的节点，即右子树中最小的节点
        // 替代节点找到后，将替代节点中的值交给待删除节点，转换成删除替代节点
        Node *leftMax = cur->_left;
        Node* parent = nullptr;
        while (leftMax->_right)
        {
            parent = leftMax;
            leftMax = leftMax->_right;
        }
        std::swap(cur->_val, leftMax->_val);
        if (parent->_left == leftMax)
        {
            parent->_left = leftMax->_left;
        }
        else
        {
            parent->_right = leftMax->_left;
        }
        std::swap(cur, leftMax);
    }
    //*********************** 要记得delete
    delete cur;
    return true;
}

template <class T>
bool BinarySearchTree<T>::_eraseR(typename BinarySearchTree<T>::Node*&root, const T &key)
{
    if (root == nullptr)
        return;
    if (root->_val > key)
        _eraseR(root->_left, key);
    else if (root->_val < t)
        _eraseR(root->_right, key);
    else
    {
        Node *del = root;
        if (root->_left == nullptr)
        {
            root = root->_right;
        }
        else if (root->_right == nullptr)
        {
            root = root->_left;
        }
        else
        {
            Node *leftMax = root->_left;
            while (leftMax->_right)
            {
                leftMax = leftMax->_right;
            }
            std::swap(leftMax->_val, root->_val);
            _eraseR(root->_left, key);
        }
        delete del;
    }
}